#include <vector>
#include <algorithm>
#include <limits>
#include <iostream>

using namespace std;

class SegmentTree {
public:
    SegmentTree(const vector<int>& data) {
        n = data.size();
        size = 1;
        while (size < n) {
            size <<= 1;
        }
        min_val.assign(2 * size, INT_MAX);
        for (int i = 0; i < n; ++i) {
            min_val[size + i] = data[i];
        }
        for (int i = size - 1; i > 0; --i) {
            min_val[i] = min(min_val[2 * i], min_val[2 * i + 1]);
        }
    }

    void update(int pos, int value) {
        pos += size;
        min_val[pos] = value;
        pos >>= 1;
        while (pos >= 1) {
            int new_val = min(min_val[2 * pos], min_val[2 * pos + 1]);
            if (min_val[pos] == new_val) {
                break;
            }
            min_val[pos] = new_val;
            pos >>= 1;
        }
    }

    int query_min(int l, int r) {
        int res = INT_MAX;
        l += size;
        r += size;
        while (l <= r) {
            if (l % 2 == 1) {
                res = min(res, min_val[l]);
                l += 1;
            }
            if (r % 2 == 0) {
                res = min(res, min_val[r]);
                r -= 1;
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }

private:
    int n, size;
    vector<int> min_val;
};

class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        int n = fruits.size();
        vector<pair<int, int>> sorted_baskets(n);
        for (int j = 0; j < n; ++j) {
            sorted_baskets[j] = {baskets[j], j};
        }
        sort(sorted_baskets.begin(), sorted_baskets.end());
        vector<int> original_to_sorted_pos(n);
        for (int k = 0; k < n; ++k) {
            int original_j = sorted_baskets[k].second;
            original_to_sorted_pos[original_j] = k;
        }
        vector<int> data(n);
        for (int k = 0; k < n; ++k) {
            data[k] = sorted_baskets[k].second;
        }
        SegmentTree st(data);
        int count = 0;
        for (int f : fruits) {
            auto it = lower_bound(sorted_baskets.begin(), sorted_baskets.end(), make_pair(f, -INT_MAX));
            int pos = distance(sorted_baskets.begin(), it);
            if (pos >= n) {
                count += 1;
                continue;
            }
            int min_idx = st.query_min(pos, n - 1);
            if (min_idx == INT_MAX) {
                count += 1;
            } else {
                int k = original_to_sorted_pos[min_idx];
                st.update(k, INT_MAX);
            }
        }
        return count;
    }
};

// 示例用法
int main() {
    Solution solution;
    vector<int> fruits1 = {6, 2, 8, 4};
    vector<int> baskets1 = {5, 3, 7, 1};
    cout << solution.numOfUnplacedFruits(fruits1, baskets1) << endl;  // 输出应为 2

    vector<int> fruits2 = {2, 1, 3, 3};
    vector<int> baskets2 = {3, 2, 1, 4};
    cout << solution.numOfUnplacedFruits(fruits2, baskets2) << endl;  // 输出应为 1

    return 0;
}